1750 #include "types.h"
1751 #include "defs.h"
1752 #include "param.h"
1753 #include "mmu.h"
1754 #include "x86.h"
1755 #include "proc.h"
1756 #include "spinlock.h"
1757 
1758 
1759 
1760 struct {
1761   struct spinlock lock;
1762   struct proc proc[NPROC];
1763 } ptable;
1764 
1765 static struct proc *initproc;
1766 
1767 int nextpid = 1;
1768 extern void forkret(void);
1769 extern void trapret(void);
1770 
1771 static void wakeup1(void *chan);
1772 
1773 void
1774 pinit(void)
1775 {
1776   initlock(&ptable.lock, "ptable");
1777 }
1778 
1779 
1780 
1781 
1782 // Print a process listing to console.  For debugging.
1783 // Runs when user types ^P on console.
1784 // No lock to avoid wedging a stuck machine further.
1785 void
1786 procdump(void)
1787 {
1788   static char *states[] = {
1789   [UNUSED]    "unused",
1790   [EMBRYO]    "embryo",
1791   [SLEEPING]  "sleep ",
1792   [RUNNABLE]  "runble",
1793   [RUNNING]   "run   ",
1794   [ZOMBIE]    "zombie"
1795   };
1796   int i;
1797   struct proc *p;
1798   char *state;
1799   uint pc[10];
1800   for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
1801     if(p->state == UNUSED)
1802       continue;
1803     if(p->state >= 0 && p->state < NELEM(states) && states[p->state])
1804       state = states[p->state];
1805     else
1806       state = "???";
1807     cprintf("%d %s %s", p->pid, state, p->name);
1808     if(p->state == SLEEPING){
1809       getcallerpcs((uint*)p->context->ebp+2, pc);
1810       for(i=0; i<10 && pc[i] != 0; i++)
1811         cprintf(" %p", pc[i]);
1812     }
1813     cprintf("\n");
1814   }
1815 }
1816 
1817 
1818 // Look in the process table for an UNUSED proc.
1819 // If found, change state to EMBRYO and return it.
1820 // Otherwise return 0.
1821 static struct proc*
1822 allocproc(void)
1823 {
1824   struct proc *p;
1825   char *sp;
1826 
1827   acquire(&ptable.lock);
1828   for(p = ptable.proc; p < &ptable.proc[NPROC]; p++)
1829     if(p->state == UNUSED)
1830       goto found;
1831   release(&ptable.lock);
1832   return 0;
1833 
1834 found:
1835   p->state = EMBRYO;
1836   p->pid = nextpid++;
1837   release(&ptable.lock);
1838 
1839   // Allocate kernel stack if possible.
1840   if((p->kstack = kalloc()) == 0){
1841     p->state = UNUSED;
1842     return 0;
1843   }
1844   sp = p->kstack + KSTACKSIZE;
1845 
1846   // Leave room for trap frame.
1847   sp -= sizeof *p->tf;
1848   p->tf = (struct trapframe*)sp;
1849 
1850   // Set up new context to start executing at forkret,
1851   // which returns to trapret (see below).
1852   sp -= 4;
1853   *(uint*)sp = (uint)trapret;
1854 
1855   sp -= sizeof *p->context;
1856   p->context = (struct context*)sp;
1857   memset(p->context, 0, sizeof *p->context);
1858   p->context->eip = (uint)forkret;
1859   p-> ctime = sys_uptime();
1860   p->priority = 1;
1861   return p;
1862 }
1863 
1864 // Set up first user process.
1865 void
1866 userinit(void)
1867 {
1868   struct proc *p;
1869   extern char _binary_initcode_start[], _binary_initcode_size[];
1870 
1871   p = allocproc();
1872   initproc = p;
1873   if(!(p->pgdir = setupkvm()))
1874     panic("userinit: out of memory?");
1875   inituvm(p->pgdir, _binary_initcode_start, (int)_binary_initcode_size);
1876   p->sz = PGSIZE;
1877   memset(p->tf, 0, sizeof(*p->tf));
1878   p->tf->cs = (SEG_UCODE << 3) | DPL_USER;
1879   p->tf->ds = (SEG_UDATA << 3) | DPL_USER;
1880   p->tf->es = p->tf->ds;
1881   p->tf->ss = p->tf->ds;
1882   p->tf->eflags = FL_IF;
1883   p->tf->esp = PGSIZE;
1884   p->tf->eip = 0;  // beginning of initcode.S
1885 
1886   safestrcpy(p->name, "initcode", sizeof(p->name));
1887   p->cwd = namei("/");
1888 
1889   p->state = RUNNABLE;
1890   p->ctime = sys_uptime();
1891   //initializing creation time
1892 
1893 }
1894 
1895 
1896 
1897 
1898 
1899 
1900 // Grow current process's memory by n bytes.
1901 // Return 0 on success, -1 on failure.
1902 int
1903 growproc(int n)
1904 {
1905   uint sz = proc->sz;
1906   if(n > 0){
1907     if(!(sz = allocuvm(proc->pgdir, sz, sz + n)))
1908       return -1;
1909   } else if(n < 0){
1910     if(!(sz = deallocuvm(proc->pgdir, sz, sz + n)))
1911       return -1;
1912   }
1913   proc->sz = sz;
1914   switchuvm(proc);
1915   return 0;
1916 }
1917 
1918 // Create a new process copying p as the parent.
1919 // Sets up stack to return as if from system call.
1920 // Caller must set state of returned proc to RUNNABLE.
1921 int
1922 fork(void)
1923 {
1924   int i, pid;
1925   struct proc *np;
1926 
1927   // Allocate process.
1928   if((np = allocproc()) == 0)
1929     return -1;
1930 
1931   // Copy process state from p.
1932   if(!(np->pgdir = copyuvm(proc->pgdir, proc->sz))){
1933     kfree(np->kstack);
1934     np->kstack = 0;
1935     np->state = UNUSED;
1936     return -1;
1937   }
1938   np->sz = proc->sz;
1939   np->parent = proc;
1940   *np->tf = *proc->tf;
1941 
1942   // Clear %eax so that fork returns 0 in the child.
1943   np->tf->eax = 0;
1944 
1945   for(i = 0; i < NOFILE; i++)
1946     if(proc->ofile[i])
1947       np->ofile[i] = filedup(proc->ofile[i]);
1948   np->cwd = idup(proc->cwd);
1949 
1950   pid = np->pid;
1951   np->state = RUNNABLE;
1952 //   np->ctime = sys_uptime();
1953   safestrcpy(np->name, proc->name, sizeof(proc->name));
1954   return pid;
1955 }
1956 
1957 // Exit the current process.  Does not return.
1958 // An exited process remains in the zombie state
1959 // until its parent calls wait() to find out it exited.
1960 void
1961 exit(void)
1962 {
1963   struct proc *p;
1964   int fd;
1965 
1966   if(proc == initproc)
1967     panic("init exiting");
1968 
1969   // Close all open files.
1970   for(fd = 0; fd < NOFILE; fd++){
1971     if(proc->ofile[fd]){
1972       fileclose(proc->ofile[fd]);
1973       proc->ofile[fd] = 0;
1974     }
1975   }
1976 
1977   iput(proc->cwd);
1978   proc->cwd = 0;
1979 
1980   proc->etime = sys_uptime();
1981   acquire(&ptable.lock);
1982 
1983   // Parent might be sleeping in wait().
1984   wakeup1(proc->parent);
1985 
1986   // Pass abandoned children to init.
1987   for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
1988     if(p->parent == proc){
1989       p->parent = initproc;
1990       if(p->state == ZOMBIE)
1991         wakeup1(initproc);
1992     }
1993   }
1994 
1995   // Jump into the scheduler, never to return.
1996   proc->state = ZOMBIE;
1997   sched();
1998   panic("zombie exit");
1999 }
2000 // Wait for a child process to exit and return its pid.
2001 // Return -1 if this process has no children.
2002 int
2003 wait(void)
2004 {
2005   struct proc *p;
2006   int havekids, pid;
2007 
2008   acquire(&ptable.lock);
2009   for(;;){
2010     // Scan through table looking for zombie children.
2011     havekids = 0;
2012     for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
2013       if(p->parent != proc)
2014         continue;
2015       havekids = 1;
2016       if(p->state == ZOMBIE){
2017         // Found one.
2018         pid = p->pid;
2019         kfree(p->kstack);
2020         p->kstack = 0;
2021         freevm(p->pgdir);
2022         p->state = UNUSED;
2023         p->pid = 0;
2024         p->parent = 0;
2025         p->name[0] = 0;
2026         p->killed = 0;
2027         release(&ptable.lock);
2028         return pid;
2029       }
2030     }
2031 
2032     // No point waiting if we don't have any children.
2033     if(!havekids || proc->killed){
2034       release(&ptable.lock);
2035       return -1;
2036     }
2037 
2038     // Wait for children to exit.  (See wakeup1 call in proc_exit.)
2039     sleep(proc, &ptable.lock);  //DOC: wait-sleep
2040   }
2041 }
2042 
2043 
2044 
2045 
2046 
2047 
2048 
2049 
2050 int
2051 wait2(int *wtime, int *rtime)
2052 {
2053 	struct proc *p;
2054 	int havekids, pid;
2055 
2056 	acquire(&ptable.lock);
2057 	for(;;){
2058     // Scan through table looking for zombie children.
2059 		havekids = 0;
2060 		for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
2061 			if(p->parent != proc)
2062 				continue;
2063 			havekids = 1;
2064 			if(p->state == ZOMBIE){
2065         // Found one.
2066 				pid = p->pid;
2067 				kfree(p->kstack);
2068 				p->kstack = 0;
2069 				freevm(p->pgdir);
2070 				p->state = UNUSED;
2071 				p->pid = 0;
2072 				p->parent = 0;
2073 				p->name[0] = 0;
2074 				p->killed = 0;
2075 				*wtime = sys_uptime()- p->ctime - p->rtime;
2076 				*rtime = p->rtime;
2077 				release(&ptable.lock);
2078 				return pid;
2079 			}
2080 		}
2081 
2082     // No point waiting if we don't have any children.
2083 		if(!havekids || proc->killed){
2084 			release(&ptable.lock);
2085 			return -1;
2086 		}
2087 
2088     // Wait for children to exit.  (See wakeup1 call in proc_exit.)
2089 		sleep(proc, &ptable.lock);  //DOC: wait-sleep
2090 	}
2091 }
2092 
2093 
2094 
2095 
2096 
2097 
2098 
2099 
2100 int
2101 nice(void){
2102     if (proc->priority > 0){
2103     	proc->priority = proc->priority - 1;
2104 	return 0;
2105     }
2106     return -1;
2107 }
2108 
2109 
2110 
2111 // Per-CPU process scheduler.
2112 // Each CPU calls scheduler() after setting itself up.
2113 // Scheduler never returns.  It loops, doing:
2114 //  - choose a process to run
2115 //  - swtch to start running that process
2116 //  - eventually that process transfers control
2117 //      via swtch back to the scheduler.
2118 void
2119 scheduler(void)
2120 {
2121   struct proc *p;
2122  int startTime;
2123 
2124   for( ; ; ){
2125     // Enable interrupts on this processor.
2126     sti();
2127 
2128     // Loop over process table looking for process to run.
2129     acquire(&ptable.lock);
2130 
2131 
2132     for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
2133       if(p->state != RUNNABLE)
2134         continue;
2135 
2136       // Switch to chosen process.  It is the process's job
2137       // to release ptable.lock and then reacquire it
2138       // before jumping back to us.
2139       proc = p;
2140       switchuvm(p);
2141 
2142       p->state = RUNNING;
2143       startTime = sys_uptime();
2144       swtch(&cpu->scheduler, proc->context);
2145       switchkvm();
2146 
2147 
2148 
2149 
2150       // Process is done running for now.
2151       // It should have changed its p->state before coming back.
2152       proc->rtime = proc->rtime + (sys_uptime() - startTime);
2153       proc = 0;
2154 
2155     }
2156     release(&ptable.lock);
2157 
2158   }
2159 
2160 
2161 }
2162 
2163 // Enter scheduler.  Must hold only ptable.lock
2164 // and have changed proc->state.
2165 void
2166 sched(void)
2167 {
2168   int intena;
2169 
2170   if(!holding(&ptable.lock))
2171     panic("sched ptable.lock");
2172   if(cpu->ncli != 1)
2173     panic("sched locks");
2174   if(proc->state == RUNNING)
2175     panic("sched running");
2176   if(readeflags()&FL_IF)
2177     panic("sched interruptible");
2178   intena = cpu->intena;
2179   swtch(&proc->context, cpu->scheduler);
2180   cpu->intena = intena;
2181 }
2182 
2183 // Give up the CPU for one scheduling round.
2184 void
2185 yield(void)
2186 {
2187   acquire(&ptable.lock);  //DOC: yieldlock
2188   proc->state = RUNNABLE;
2189 
2190   sched();
2191   release(&ptable.lock);
2192 }
2193 
2194 
2195 
2196 
2197 
2198 
2199 
2200 // A fork child's very first scheduling by scheduler()
2201 // will swtch here.  "Return" to user space.
2202 void
2203 forkret(void)
2204 {
2205   // Still holding ptable.lock from scheduler.
2206   release(&ptable.lock);
2207 
2208   // Return to "caller", actually trapret (see allocproc).
2209 }
2210 
2211 // Atomically release lock and sleep on chan.
2212 // Reacquires lock when awakened.
2213 void
2214 sleep(void *chan, struct spinlock *lk)
2215 {
2216   if(proc == 0)
2217     panic("sleep");
2218 
2219   if(lk == 0)
2220     panic("sleep without lk");
2221 
2222   // Must acquire ptable.lock in order to
2223   // change p->state and then call sched.
2224   // Once we hold ptable.lock, we can be
2225   // guaranteed that we won't miss any wakeup
2226   // (wakeup runs with ptable.lock locked),
2227   // so it's okay to release lk.
2228   if(lk != &ptable.lock){  //DOC: sleeplock0
2229     acquire(&ptable.lock);  //DOC: sleeplock1
2230     release(lk);
2231   }
2232 
2233   // Go to sleep.
2234   proc->chan = chan;
2235   proc->state = SLEEPING;
2236   sched();
2237 
2238   // Tidy up.
2239   proc->chan = 0;
2240 
2241   // Reacquire original lock.
2242   if(lk != &ptable.lock){  //DOC: sleeplock2
2243     release(&ptable.lock);
2244     acquire(lk);
2245   }
2246 }
2247 
2248 
2249 
2250 // Wake up all processes sleeping on chan.
2251 // The ptable lock must be held.
2252 static void
2253 wakeup1(void *chan)
2254 {
2255   struct proc *p;
2256 
2257   for(p = ptable.proc; p < &ptable.proc[NPROC]; p++)
2258     if(p->state == SLEEPING && p->chan == chan)
2259       p->state = RUNNABLE;
2260 }
2261 
2262 // Wake up all processes sleeping on chan.
2263 void
2264 wakeup(void *chan)
2265 {
2266   acquire(&ptable.lock);
2267   wakeup1(chan);
2268   release(&ptable.lock);
2269 }
2270 
2271 // Kill the process with the given pid.
2272 // Process won't exit until it returns
2273 // to user space (see trap in trap.c).
2274 int
2275 kill(int pid)
2276 {
2277   struct proc *p;
2278 
2279   acquire(&ptable.lock);
2280   for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
2281     if(p->pid == pid){
2282       p->killed = 1;
2283       p->etime = sys_uptime();
2284       // Wake process from sleep if necessary.
2285       if(p->state == SLEEPING)
2286         p->state = RUNNABLE;
2287       release(&ptable.lock);
2288       return 0;
2289     }
2290   }
2291   release(&ptable.lock);
2292   return -1;
2293 }
2294 
2295 
2296 
2297 
2298 
2299 
